Gelfond and Lifschitz proposed the notion of a stable model of a logic program. We establish that the set of all stable models in a Herbrand universe of a recursive logic program is, up to recursive renaming, the set of all infinite paths of a recursive, countably branching tree, and conversely. As a consequence, the problem, given a recursive logic program, of determining whether it has at least one stable model, is Σ11-complete. Due to (...) the equivalences established in the authors' previous nonmonotone rule systems papers ), this applies equally to truth maintenance systems and default logics. (shrink)

This paper, a contribution to “micro set theory”, is the study promised by the first author in [M4], as improved and extended by work of the second. We use the rudimentarily recursive functions and the slightly larger collection of gentle functions to initiate the study of provident sets, which are transitive models of $\mathsf{PROVI}$, a subsystem of $\mathsf{KP}$ whose minimal model is Jensen’s $J_{\omega}$. $\mathsf{PROVI}$ supports familiar definitions, such as rank, transitive closure and ordinal addition—though not ordinal multiplication—and (...) Shoenfield’s unramified forcing. Providence is preserved under directed unions. An arbitrary set has a provident closure, and the extension of a provident $M$ by a set-generic $\mathcal{G}$ is the provident closure of $M\cup\{\mathcal{G}\}$. The improvidence of many models of $\mathsf{Z}$ is shown. The final section uses similar but simpler recursions to show, in the weak system $\mathsf{MW}$, that the truth predicate for $\dot{\varDelta}_{0}$ formulæ is $\Delta_{1}$. (shrink)

We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in "propositional" fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The "pure," propositional fragment FLR 0 turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of (...) models. (shrink)

We study logical systems for reasoning about equations involving recursive definitions. In particular, we are interested in "propositional" fragments of the functional language of recursion FLR [18, 17], i.e., without the value passing or abstraction allowed in FLR. The "pure," propositional fragment FLR$_0$ turns out to coincide with the iteration theories of [1]. Our main focus here concerns the sharp contrast between the simple class of valid identities and the very complex consequence relation over several natural classes of models.

The abstract basis of modern computation is the formal description of a finite state machine, the Universal Turing Machine, based on manipulation of integers and logic symbols. In this contribution to the discourse on the computer-brain analogy, we discuss the extent to which analog computing, as performed by the mammalian brain, is like and unlike the digital computing of Universal Turing Machines. We begin with ordinary reality being a permanent dialog between continuous and discontinuous worlds. So it is with computing, (...) which can be analog or digital, and is often mixed. The theory behind computers is essentially digital, but efficient simulations of phenomena can be performed by analog devices; indeed, any physical calculation requires implementation in the physical world and is therefore analog to some extent, despite being based on abstract logic and arithmetic. The mammalian brain, comprised of neuronal networks, functions as an analog device and has given rise to artificial neural networks that are implemented as digital algorithms but function as analog models would. Analog constructs compute with the implementation of a variety of feedback and feedforward loops. In contrast, digital algorithms allow the implementation of recursive processes that enable them to generate unparalleled emergent properties. We briefly illustrate how the cortical organization of neurons can integrate signals and make predictions analogically. While we conclude that brains are not digital computers, we speculate on the recent implementation of human writing in the brain as a possible digital path that slowly evolves the brain into a genuine (slow) Turing machine. (shrink)

Models of normal open induction are those normal discretely ordered rings whose nonnegative part satisfy Peano's axioms for open formulas in the language of ordered semirings. (Where normal means integrally closed in its fraction field.) In 1964 Shepherdson gave a recursive nonstandard model of open induction. His model is not normal and does not have any infinite prime elements. In this paper we present a recursive nonstandard model of normal open induction with an unbounded set (...) of infinite prime elements. (shrink)

The study of plant signaling and behaviour, whose aim is to address the physiological basis for adaptive behaviour in plants, is a growing and thought-provoking field of research. In this review we discuss relevant studies that try to interpret in a neurocognitive fashion cases in which plants seem to behave similarly to animals. By comparing observations and experiments about plants and animals, we propose a framework composed of three axes in which interactions of living organisms with the world can be (...) represented. The first axis refers to adaptiveness, the second to sensitivity, and the third to sentience. This model allows us to interpret the behaviours of living organisms along a continuum capable of giving a smooth transition from simple to complex responses. In light of this, plants show an excellent adaptiveness, a variable level of sensitivity, and a good degree of sentience (restricted to the immediate perception that something is happening to themselves). Only the organisms with a high degree of sentience can have the basis for developing consciousness. However, even though it is necessary for consciousness, sentience is not sufficient, as it must be associated with a complex functional organization of structures that can support a recursive and synchronized processing of information. So far, plants have been found to completely lack this type of organization. Plants appear to be, therefore, sentient but not conscious. (shrink)

α-recursion lifts classical recursion theory from the first transfinite ordinal ω to an arbitrary admissible ordinal α [10]. Idealized computational models for α-recursion analogous to Turing machine models for classical recursion have been proposed and studied [4] and [5] and are applicable in computational approaches to the foundations of logic and mathematics [8]. They also provide a natural setting for modeling extensions of the algorithmic logic described in [1] and [2]. On such models, an α-Turing machine can complete a θ-step (...) computation for any ordinal θ < α. Here we consider constraints on the physical realization of α-Turing machines that arise from the structure of physical spacetime. In particular, we show that an α-Turing machine is realizable in a spacetime constructed from R only if α is countable. While there are spacetimes where uncountable computations are possible and while they may even be empirically distinguishable from a standard spacetime, there is good reason to suppose that such nonstandard spacetimes are nonphysical. We conclude with a suggestion for a revision of Church’s thesis appropriate as an upper bound for physical computation. (shrink)

We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.

We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and (...) BΣ n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + IΣ 2 + RT 2 2 is conservative over RCA 0 + IΣ 2 for Π 1 1 statements and that $RCA_0 + I\Sigma_3 + RT^2_{ , is Π 1 1 -conservative over RCA 0 + IΣ 3 . It follows that RCA 0 + RT 2 2 does not imply BΣ 3 . In contrast, J. Hirst showed that $RCA_0 + RT^2_{ does imply BΣ 3 , and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{ is strictly stronger than RT 2 2 over RCA 0. (shrink)

Several writers have assumed that when in “Outline of a Theory of Truth” I wrote that “the orthodox approach” – that is, Tarski’s account of the truth definition – admits descending chains, I was relying on a simple compactness theorem argument, and that non-standard models must result. However, I was actually relying on a paper on ‘pseudo-well-orderings’ by Harrison. The descending hierarchy of languages I define is a standard model. Yablo’s Paradox later emerged as a key to interpreting the (...) result. (shrink)

We define and study the class of all stack algebras as the class of all minimal algebras in a variety defined by an infinite recursively enumerable set of equations. Among a number of results, we show that the initial model of the variety is computable, that its equational theory is decidable, but that its equational deduction problem is undecidable. We show that it cannot be finitely axiomatised by equations, but it can be finitely axiomatised by equations with a hidden (...) sort and functions. This class of all stack algebras, together with its specifications, can be used to survey the many models in the literature on stacks in a systematic way, and hence give the study of the stack some mathematical coherence. Article Outline. (shrink)

We describe a strongly minimal theory S in an effective language such that, in the chain of countable models of S, only the second model has a computable presentation. Thus there is a spectrum of an -categorical theory which is neither upward nor downward closed. We also give an upper bound on the complexity of spectra.

We employ an infinite-signature Hrushovski amalgamation construction to yield two results in Recursive Model Theory. The first result, that there exists a strongly minimal theory whose only recursively presentable models are the prime and saturated models, adds a new spectrum to the list of known possible spectra. The second result, that there exists a strongly minimal theory in a finite language whose only recursively presentable model is saturated, gives the second non-trivial example of a spectrum produced in (...) a finite language. (shrink)

Social networks play a significant role in learning and thus in farmers’ adoption of new agricultural technologies. This study examined the effects of social network factors on information acquisition and adoption of new seed varieties among groundnut farmers in Uganda and Kenya. The data were generated through face-to-face interviews from a random sample of 461 farmers, 232 in Uganda and 229 in Kenya. To assess these effects two alternative econometric models were used: a seemingly unrelated bivariate probit model and (...) a recursive bivariate probit model. The statistical evaluation of the SUBP shows that information acquisition and adoption decisions are interrelated while tests for the RBP do not support this latter model. Therefore, the analysis is based on the results obtained from the SUBP. These results reveal that social network factors, particularly weak ties with external support, partially influence information acquisition, but do not influence adoption. In Uganda, external support, gender, farm size, and geographic location have an impact on information acquisition. In Kenya, external support and geographic location also have an impact on information acquisition. With regard to adoption, gender, household size, and geographic location play the most important roles for Ugandan farmers, while in Kenya information from external sources, education, and farm size affect adoption choice. The study provides insight on the importance of external weak ties in groundnut farming, and a need to understand regional differences along gender lines while developing agricultural strategies. This study further illustrates the importance of farmer participation in applied technology research and the impact of social interactions among farmers and external agents. (shrink)

We construct two recursive models of fragments of set theory. We also show that the fragments of Kripke-Platek set theory that prove -induction for -formulas have no recursive models but the standard model of the hereditarily finite sets.

The technique of forcing is almost ubiquitous in set theory, and it seems to be based on technicalities like the concepts of genericity, forcing names and their evaluations, and on the recursively defined forcing predicates, the definition of which is particularly intricate for the basic case of atomic first order formulas. In his [3], the first author has provided an axiomatic framework for set forcing over models of $\mathrm {ZFC}$ that is a collection of guiding principles for extensions over which (...) one still has control from the ground model, and has shown that these axiomatics necessarily lead to the usual concepts of genericity and of forcing extensions, and also that one can infer from them the usual recursive definition of forcing predicates. In this paper, we present a more general such approach, covering both class forcing and set forcing, over various base theories, and we provide additional details regarding the formal setting that was outlined in [3]. (shrink)

Behavior oftentimes allows for many possible interpretations in terms of mental states, such as goals, beliefs, desires, and intentions. Reasoning about the relation between behavior and mental states is therefore considered to be an effortful process. We argue that people use simple strategies to deal with high cognitive demands of mental state inference. To test this hypothesis, we developed a computational cognitive model, which was able to simulate previous empirical findings: In two-player games, people apply simple strategies at first. (...) They only start revising their strategies when these do not pay off. The model could simulate these findings by recursively attributing its own problem solving skills to the other player, thus increasing the complexity of its own inferences. The model was validated by means of a comparison with findings from a developmental study in which the children demonstrated similar strategic developments. (shrink)

Behavior oftentimes allows for many possible interpretations in terms of mental states, such as goals, beliefs, desires, and intentions. Reasoning about the relation between behavior and mental states is therefore considered to be an effortful process. We argue that people use simple strategies to deal with high cognitive demands of mental state inference. To test this hypothesis, we developed a computational cognitive model, which was able to simulate previous empirical findings: In two-player games, people apply simple strategies at first. (...) They only start revising their strategies when these do not pay off. The model could simulate these findings by recursively attributing its own problem solving skills to the other player, thus increasing the complexity of its own inferences. The model was validated by means of a comparison with findings from a developmental study in which the children demonstrated similar strategic developments. (shrink)

Behavior oftentimes allows for many possible interpretations in terms of mental states, such as goals, beliefs, desires, and intentions. Reasoning about the relation between behavior and mental states is therefore considered to be an effortful process. We argue that people use simple strategies to deal with high cognitive demands of mental state inference. To test this hypothesis, we developed a computational cognitive model, which was able to simulate previous empirical findings: In two-player games, people apply simple strategies at first. (...) They only start revising their strategies when these do not pay off. The model could simulate these findings by recursively attributing its own problem solving skills to the other player, thus increasing the complexity of its own inferences. The model was validated by means of a comparison with findings from a developmental study in which the children demonstrated similar strategic developments. (shrink)

A collection of 24 out of the 35 papers presented at the Fourth Scandinavian Logic Symposium and First Soviet-Finnish Logic Conference, which took place simultaneously in Finland in 1976. Topics covered are proof theory, set theory, model theory, recursion theory, infinitary languages, generalized quantifiers, truthlikeness, natural language, and "philosophical logic." There is a paper by George Kreisel which discusses an intriguing distinction between the theory of proofs and general proof theory, the latter being the study of the allegedly definitional (...) or essential property of proofs, the former being the study of structural features such as length of proofs and of relations between proofs and other things. There is a paper by Hintikka in which he applies his "game-theoretical semantics" developed elsewhere to quantifiers in natural languages, e.g., the analysis of sentences like "some novel by every novelist is mentioned by every critic". I found the most interesting paper to be the one by Bengt Hansson, which studies the nature of paradoxes by articulating an analogy with mathematical equations, the crucial property about the latter being that they do not always have solutions. Almost all papers are highly technical and thus aimed at experts of the specialties mentioned in the book’s title.—M.A.F. (shrink)

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

We develop the theory of partial satisfaction relations for structures that may be proper classes and define a satisfaction predicate ($\models^*$) appropriate to such structures. We indicate the utility of this theory as a framework for the development of the metatheory of first-order predicate logic and set theory, and we use it to prove that for any recursively enumerable extension $\Theta$ of ZF there is a finitely axiomatizable extension $\Theta'$ of GB that is a conservative extension of $\Theta$. We also (...) prove a conservative extension result that justifies the use of $\models^*$ to characterize ground models for forcing constructions. (shrink)

A method for the recursive identification of physiological models of the cardiovascular baroreflex is proposed and applied to the time-varying analysis of vagal and sympathetic activities. The proposed method was evaluated with data from five newborn lambs, which were acquired during injection of vasodilator and vasoconstrictors and the results show a close match between experimental and simulated signals. The model-based estimation of vagal and sympathetic contributions were consistent with physiological knowledge and the obtained estimators of vagal and sympathetic (...) activities were compared to traditional markers associated with baroreflex sensitivity. High correlations were observed between traditional markers and model-based indices. (shrink)

Cumulative evidence suggests that, for children and adolescents, peer relatedness is an essential component of their overall sense of belonging, and correlates with subjective well-being and school-based well-being. However, it remains unclear what the underlying mechanism explaining these relationships is. Therefore, this study examines whether there is a reciprocal effect between school satisfaction and overall life satisfaction, and whether the effect of peer relatedness on life satisfaction is mediated by school satisfaction. A non-recursive model with instrumental variables was (...) tested with econometric and structural equation modeling methodologies, using a cross-sectional sample of n = 5,619 Chilean early adolescents, aged 10, 11, and 12. Results were highly consistent across methods and supported the hypotheses. First, the findings confirmed a significant reciprocal influence between school satisfaction and overall life satisfaction, with a greater impact from school to life satisfaction. Second, the effect of peer relatedness on overall life satisfaction was fully mediated by school satisfaction. The study further suggests the importance of considering reciprocal effects among domain-specific satisfaction and overall life satisfaction and illustrates the application of non-recursive models for this purpose. (shrink)

In 1952, Heinrich Scholz published a question in The Journal of Symbolic Logic asking for a characterization of spectra, i.e., sets of natural numbers that are the cardinalities of finite models of first order sentences. Günter Asser in turn asked whether the complement of a spectrum is always a spectrum. These innocent questions turned out to be seminal for the development of finite model theory and descriptive complexity. In this paper we survey developments over the last 50-odd years pertaining (...) to the spectrum problem. Our presentation follows conceptual developments rather than the chronological order. Originally a number theoretic problem, it has been approached by means of recursion theory, resource bounded complexity theory, classification by complexity of the defining sentences, and finally by means of structural graph theory. Although Scholz' question was answered in various ways, Asser's question remains open. (shrink)

The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models (...) of arithmetic. (shrink)

Repetitive negative thinking (RNT) describes a recursive, unproductive pattern of thought that is commonly observed in individuals who experience anxiety and depression. Past research on RNT has primarily relied on self-report, which fails to capture the potential mechanisms that underlie the persistence of maladaptive thought. We investigated whether RNT may be maintained by a negatively biased semantic network. The present study used a modified free association task to assess state RNT. Following the presentation of a valenced (positive, neutral, negative) (...) cue word, participants generated a series of free associates, which allowed for the dynamic progression of responses. State RNT was conceptualised as the length of consecutive, negatively valenced free associates (i.e. chains). Participants also completed two self-report measures that assessed trait RNT and trait negative affect. Within a structural equation model, negative (but not positive or neutral) response chain length positively predicted trait RNT and negative affect, and this was only the case for positive (but not negative or neutral) cue words. These results suggest that RNT tendencies may be reflected in semantic retrieval and can be assessed without self-report. (shrink)

The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given which distinguish primitive (...) recursive structures, exponential-time structures and structures with honest witnesses. (shrink)

The main result of this paper partially answers a question raised in about the existence of countable just recursively saturated models of Peano Arithmetic with non‐isomorphic automorphism groups. We show the existence of infinitely many countable just recursively saturated models of Peano Arithmetic such that their automorphism groups are not topologically isomorphic. We also discuss maximal open subgroups of the automorphism group of a countable arithmetically saturated model of in a very good interstice.

This paper presents an approach to the belief system based on a computational framework in three levels: first, the logic level with the definition of binary local rules, second, the arithmetic level with the definition of recursive functions and finally the behavioural level with the definition of a recursive construction pattern. Social communication is achieved when different beliefs are expressed, modified, propagated and shared through social nets. This approach is useful to mimic the belief system because the defined (...) functions provide different ways to process the same incoming information as well as a means to propagate it. Our model also provides a means to cross different beliefs so, any incoming information can be processed many times by the same or different functions as it occurs is social nets. (shrink)

I survey the syntactic technique of tiering which can be used to restrict the power of a recursion scheme. I show how various results can be obtained entirely proof theoretically without the use of a model of computation.

This paper presents an approach to the belief system based on a computational framework in three levels: first, the logic level with the definition of binary local rules, second, the arithmetic level with the definition of recursive functions and finally the behavioural level with the definition of a recursive construction pattern. Social communication is achieved when different beliefs are expressed, modified, propagated and shared through social nets. This approach is useful to mimic the belief system because the defined (...) functions provide different ways to process the same incoming information as well as a means to propagate it. Our model also provides a means to cross different beliefs so, any incoming information can be processed many times by the same or different functions as it occurs is social nets. (shrink)

Mathematics is obviously important in the sciences. And so it is likely to be equally important in any effort that aims to understand God in a scientifically significant way or that aims to clarify the relations between science and theology. The degree to which God has any perfection is absolutely infinite. We use contemporary mathematics to precisely define that absolute infinity. For any perfection, we use transfinite recursion to define an endlessly ascending series of degrees of that perfection. That series (...) rises to an absolutely infinite degree of that perfection. God has that absolutely infinite degree. We focus on the perfections of knowledge, power, and benevolence. Our model of divine infinity thus builds a bridge between mathematics and theology. (shrink)